package leetcode.medium.q16;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().threeSumClosest(new int[]{0,3,97,102,200}, 300));
    }
}

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int best = 99999;

        //1.循环一个num[i]作为a,内层做target-num[i]接近b+c的比较
        for (int i = 0; i < nums.length - 2; i++) {
            int a = nums[i];

            //3.优化：如果开始就大了，就没必要继续走#2了
            if (best > target && (nums[i] + nums[i + 1] + nums[i + 2]) >= best) {
                break;
            }
            //2.b= nums[j], c=nums[k]
            for (int j = i + 1, k = nums.length - 1; j < k; ) {
                int sum = nums[j] + nums[k] + a;
                if (Math.abs(target - best) > Math.abs(target - sum)) {
                    best = sum;
                }
                if (sum > target) {
                    k--;
                } else if (sum < target) {
                    j++;
                } else {
                    //==?
                    break;
                }

            }

        }

        return best;
    }
}
